1. Field of the Invention
This invention relates to method and system for generation of a quadratic curve signal to be used effectively for expression of quadratic curves, including a straight line, in an aggregate of dots.
A display unit (e.g. plasma display unit and cathode ray tube (CRT) of a raster scan system) expressing patterns in an aggregate of dots and a digital plotter are used in electronic computer systems, as a pattern output device. In case a human being utilizes a computer in a conversational mode through a display unit, such as for example, in computer aid design (CAD), a high speed, accurate and easy to observe curve, must be generated on the CRT. More particularly, the present invention relates to method and system for generation of a quadratic curve signal, which satisfies such requirements. The curve herein disclosed refers to a conic curve, including a straight line.
2. Description of the Prior Art
One method for generating curves at high speed utilizes a device known as digital differential analyzer (DDA). This method is described in detail in IEEE Transaction on Computers, November 1975, P. 1109-1110, "On Digital Differential Analyzer Circle Generation for Computer Graphics" P. G. McCrea and P. W. Baker. However, according to the method described therein, generation of conic curves leaves open the possibility of producing large errors. Furthermore, disadvantageously, such a method precludes generating a curve at reasonably high speed and smoothly.
As an alternative from the foregoing method of generating parametric curves using the DDA method, a method for generating conic curves nonparametrically is disclosed, for example, in IEEE Transaction on Computers, September 1970, P. 783-793, "Incremental Curve Generation", Per E. Danielson; or in IEEE Transaction on Computers, December 1973, P. 1052-1960, "An Improved Algorithm for the Generation of Nonparametric curves",, Bernard W. Jordan, et. al.. Insofar as a straight line and circle are concerned, a simpler method is disclosed in IEEE Transaction on Computers, October 1979 P. 728-738, "A High Speed Algorithm for the Generation of Straight Lines and Circular Arcs", Yasuhito Suenaga etal.
The method disclosed by Jordan et al. is effective for generating curves which are accurate, smooth and superior in symmetricalness, in quadratic curve generation. However, that method has a shortcoming in that it requires a plurality of variable registers which involves a problem prone sequence and requires a large amount of time for processing, in the hardware carrying out the algorithm.
Thus, in the prior art, there exists a need for a simple and inexpensive method and system for generation of quadratic curves, which can be carried out readily by simple hardware and which improves upon the Jordan method, on the basis of an algorithm for the quadratic curve generation, suggested thereby.
Prior to describing the invention, the Jordan method of generating a quadratic curve will be described. FIG. 1 is an explanatory drawing of Jordan's method. FIG. 2 is a flow chart of the algorithm representing such method. In FIG. 1, there is shown the case wherein a circle is set forth as an example.
First, a two dimensional curve is given by the below expression (1). EQU f(x,y)=0 (1)
Then, a derived function is given as below expressions (2) through (6). ##EQU1## Assuming z=f(x, y), the curve f(x, y)=0, will be conceived to be an intersection with the plane x,y cut with three dimensional curves z=f(x, y) and z=0. Since values of x, y are discrete in the curve f(x, y)=0 which is expressed as a dot pattern, these do not aways appear on plane z=0, and value f(x, y) can be any of f(x, y)&gt;0, =0, &lt;0. Therefore, a dot pattern satisfying f(x, y)=0 approximately can be drawn by selecting lattice point coordinates of x, y in sequence, so that f(x, y) will be minimized.
The case wherein a circle is drawn, as an example of a quadratic curve, is shown in FIG. 1. Suppose the curve is drawn in the direction indicated by arrow from coordinates Ps. In FIG. 1, if the present spot is P, the point to move next will be either Px, Pxy or Py. However, in FIG. 1, the point present on the plane x, y is Ps only, and those points of P, Px, Pxy and Py are not always ones to appear on plane x, y. Now, if a distance from f(x, y) to f(x, y)=0, at point P is saved as f.sup..alpha., then the value f(x, y) at points Px, Pxy, Py, can be expressed by the below expressions (7) through (9). EQU f(x+.DELTA.x,y).rarw.f.alpha.+fx.multidot..DELTA.x+1/2fxx(.DELTA.x.sup.2)+ . . . (7) EQU f(x,y+.DELTA.y).rarw.f.alpha.+fy.multidot..DELTA.y+1/2fyy(.DELTA.y.sup.2)+ . . . (8) EQU f(x+.DELTA.x,Y+.DELTA.y).rarw.f.alpha.+fx.multidot..DELTA.x+fy.multidot..DE LTA.y+1/2{fxx(.DELTA.x).sup.2 +2fxy(.DELTA.x)(.DELTA.y)+fyy(.DELTA.y).sup.2 }+ . . . (9)
The above expressions (7) through (9) are calculated, then the absolute values .vertline.f.sup.X .vertline., .vertline.f.sup.Y .vertline., .vertline.f.sup.XY .vertline. are compared with each other, and then value f(x,y) is renewed as f.sup..alpha.. Next, fx and fy are renewed in below expressions (10) and (11). EQU fx.rarw.fx+fxx.multidot..DELTA.x+fxy.multidot..DELTA.y+ . . . (10) EQU fy.rarw.fy+fyx.multidot..DELTA.x+fyy.multidot..DELTA.y+ . . . (11)
The circle is drawn by repeating the above operation until the end point.
FIG. 2 is a flow chart giving an algorithm according to the described Jordan method.
The Jordan method comprises selecting from the present spot, the next point, from among three points proposed therefor. However, disadvantageously, the hardware which is required to carry out this method, involves complex circuitry having a large number of variables.
Thus, the art still is deficient in a method and system for generating quadratic curves, which are simple, and inexpensive and which can be carried out with simple and inexpensive hardware.